GATE CSE 2006
Q31.
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3-ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?Q32.
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?Q33.
We consider addition of two 2's complement numbers b_{n-1}b_{n-2}...b_{0} and a_{n-1}a_{n-2}...a_{0}. A binary Combinational Circuit for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n-1}c_{n-2}...c_{0} and the carryout by c_{out} . Which one of the following options correctly identifies the overflow condition?Q34.
Consider the following C code segment. for (i = 0, < i n; i++) { for (j=0; j< n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one to the following false?Q35.
Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n+m] be another integer array. void xyz (int a[],int b[],int c[]){ int i, j, k; i=j=k=0; while((i < n))&&(j < m) if (a[i] < b[j]c[k++]=a[i++]; else c[k++]=b[j++]; } Which of the following condition(s) hold(s) after the termination of the while loop ? I. j\ltm, k=n+j-1, and a [n-1]\ltb[j] if i=n II. i\ltn, k=m+i-1, and b[m-1]\leqa[i] if j=mQ36.
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?Q37.
Consider a weighted complete graph G on the vertex set {v_{1},v_{2},...,v_{n}} such that the weight of the edge (v_{i},v_{j}) is 2|i-j|. The weight of a minimum spanning treeQ38.
Consider these two functions and two statements S1 and S2 about them. S1 : The transformation from work 1 to work 2 is valid, i.e., for any program state and input arguments, work 2 will compute the same output and have the same effect on program state as work 1 S2 : All the transformations applied to work 1 to get work 2 will always improve the performance (i.e. reduce CPU time) of work 2 compared to work 1Q39.
A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?Q40.
Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction "bbs reg, pos, labbel" jumps to label if bit in position pos of register operand reg is one. a register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented. temp\rightarrowreg & mask Branch to label if temp is non-zero The variable temp is a temporary register. For correct emulation the variable mask must be generated by